package algotithm.leetcode.listnode.test23;

/**
 * @author zhouyanxiang
 * @Date 2021-02-2021/2/18-19:26
 * @URL https://leetcode-cn.com/problems/merge-k-sorted-lists/
 * @Title 23. 合并K个升序链表
 */

import algotithm.leetcode.listnode.ListNode;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {

    public static void main(String[] args) {
//        ListNode n1 = new ListNode(1);
//        ListNode n2 = new ListNode(4);
//        ListNode n3 = new ListNode(5);
//        n1.next = n2;
//        n2.next = n3;
////        n3.next = null;
//
//        ListNode l1 = new ListNode(1);
//        ListNode l2 = new ListNode(3);
//        ListNode l3 = new ListNode(4);
//        l1.next = l2;
//        l2.next = l3;
////        l3.next = null;
//
//        ListNode t1 = new ListNode(2);
//        ListNode t2 = new ListNode(5);
//        t1.next = t2;
////        t2.next = null;

//        ListNode[] lists = {n1,n2,n3,l1,l2,l3,t1,t2};
//        Solution solution = new Solution();
//        ListNode listNode = solution.mergeKLists(lists);
//        while (listNode != null) {
//            System.out.print(listNode.val + " ");
//            listNode = listNode.next;
//        }
    }

    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists,0,lists.length - 1);
    }

    public ListNode merge(ListNode[] lists, int l ,int r) {
        if (l == r) {
            return lists[l];
        }
        if (l > r ) {
            return null;
        }
        int mid = (l + r) >> 1;
        return mergeTwoListNode(merge(lists,l,mid),merge(lists,mid+1,r));
    }


    public ListNode mergeTwoListNode(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode node = dummy;
        ListNode t1 = l1;
        ListNode t2 = l2;
        while (t1 != null && t2 != null) {
            if (t1.val <= t2.val) {
                node.next = t1;
                t1 = t1.next;
            } else {
                node.next = t2;
                t2 = t2.next;
            }
            node = node.next;
        }
        node.next = t1 == null ? t2 : t1;
        return  dummy.next;
    }
}